#include "prefixTree.h"
#include <stdlib.h> //for malloc, memset
#include <string.h>

trieNode_t * createNode() {
    trieNode_t *newNode = (trieNode_t *) malloc(sizeof(trieNode_t));
    memset(newNode, 0, sizeof(trieNode_t));
    return newNode;
}

int isEmpty(trieNode_t *root) {
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (root->child[i] != NULL) {
            return 0;
        }
    }
    return 1;
}

void insert(trieNode_t *root, char *string) {
    int index;
    trieNode_t *currNode=root;

    for (int i = 0; i < strlen(string); i++) {
        index = string[i] - 'a';
        if (currNode->child[index] == NULL) 
            currNode->child[index] = createNode();
        currNode = currNode->child[index];
    }
    currNode->isEndOfWord = 1;
}

int search(trieNode_t *root, char *string) {
    int index;
    trieNode_t *currNode=root;

    for (int i = 0; i < strlen(string); i++) {
        index = string[i] - 'a';
        if (currNode->child[index] == NULL) 
            return 0;
        currNode = currNode->child[index];
    }
    int ret = (currNode != NULL && currNode->isEndOfWord) ? 1:0;
    return ret;
}

static trieNode_t* deleteHelper(trieNode_t *root, char *string, int depth) {
    if (root==NULL)
        return NULL;

    if (depth == strlen(string)) {
        if (root->isEndOfWord) 
            root->isEndOfWord = 0;
        if (isEmpty(root)) {
            free(root);
            return NULL;
        } 
        return root;
    } else {
        int index = string[depth] - 'a';
        root->child[index] = deleteHelper(root->child[index], string, depth + 1);
        if (isEmpty(root) && !root->isEndOfWord) {
            free(root);
            return NULL;
        } 
        return root;
    }
}

trieNode_t *delete(trieNode_t *tree, char *string) {
    deleteHelper(tree, string, 0);
}